In a digital signature scheme, a signer computes a pair of keys: a verification key and a matching signing key. The signer keeps this signing key secret and uses it in order to produce his digital signature (a string of bits) of a given message. The verification key is used by anyone who wishes to know whether a given string is the signer's digital signature of a message. Knowledge of the verification key alone is not, however, sufficient to produce correct signatures relative to the verification key. Thus, in order to enable as wide a distribution as possible for his own digital signature, the signer should make his verification key as public as possible. Therefore, verification keys are also referred to as "public keys" and signing keys are referred to as "secret keys".
Certification is a mechanism for proving that one or more characteristics of particular data are true. These characteristics may include the origin of the data and/or the identity of the originator of the dam. Particularly important are certificates that vouch that a given public key, PK.sub.i, belongs to a user, U. Such certificates, in fact, enable the correct verification of the digital signatures of user U.
Data, D, can be certified by having a multiplicity of authorities indicate their approval using their own individual digital signatures, relative to their own :individual public keys, to sign D. These signatures (and public keys) may constitute a certificate for the data. Often, these signing authorities are organized hierarchically, in which case each authority, before contributing to certify the data, may also verify whether the lower-level authorities have sufficient authority to contribute to certification of the data.
While this system keeps the authorities who have caused the issuance of a certificate for D accountable, it is quite wasteful because the issued certificate contains individual signatures of all of the relevant authorities. In addition, the certificate may also include verification keys for each of the authorities whose verification key is not either known by the recipient of the certificate or is itself certified in another manner, either within the certificate or by means of a separate certificate. This can cause certificates to become quite long.
One way to decrease the size of the certificate is to have the authorities share a signature using a threshold digital signature scheme. In a (t,n) threshold digital signature scheme, a given group of n signers share a common public key CPK, but each individual member of the group, j, has a different secret key, S.sub.j. By means of his own S.sub.j, an individual signer, j, may produce his own partial signature (which cannot be forged by anyone else) for particular data, D. If t or more individual members correctly partially sign D, then their partial signatures can be easily combined so as to produce a digital signature of D that can be verified relative to CPK. On the other hand, the scheme is such that no set of less than t correct partial signatures of D can be combined to yield a correct signature of D relative to CPK. Thus, a correct signature of D relative to CPK proves that at least t of the n signers approved D. Such a single (combined) signature of D (relative to CPK) is typically more compact than t individual signatures of D. Several methods have been suggested for achieving such threshold signatures. See, for example, Harn, "Group-oriented (t,n) threshold digital signature scheme and digital multisignature", IEE Proc.-Comput. Digit. Tech. Vol. 141, No.5, 307-313 (Sept. 1994) and Gennaro et al., "Robust Threshold DSS Signatures", EuroCrypt 96.
While a (t,n) threshold signature of D vouches compactly for the fact that at least t out the n designated members approved D, it does not provide accountability of the at least t members who provided the necessary partial signatures of D. In fact, once the partial signatures of D are combined into a single signature of D relative to CPK, it cannot be determined which members approved D. The process of generating a signature of D relative to CPK is transparent to the verifier of the signature.
Because of the lack of accountability, producing a combined (t,n) threshold-signature of D relative to a given common key CPK (universally known or otherwise certified) is not in many instances a suitable method for certifying D. Without accountability, t out of the n certifying authorities could provide partial signatures for false data and then deny, with impunity, having caused the certification.
A (t,n) threshold signature scheme keeps all the signers accountable when n=t. If an (n,n) threshold signature of D relative to CPK has been produced, then all n authorities must have approved D, because all n authorities must have contributed their own partial signatures of D. Therefore, none of the individual signatories can deny having contributed to the certification. Unfortunately, however, in many cases an (n,n) threshold signature schemes is not adequate for certification purposes. A certification scheme may include many certification authorities of various types. A large organization could have one hundred or more certifying authorities. It could therefore be impractical to require all of them approve each item of data to be certified by partially signing it.
It is thus desirable to develop a practical way to produce compact certificates by means of threshold signatures in a way that maintains accountability of the authorities who cause a given certificate to be issued.